﻿#define _CRT_SECURE_NO_WARNINGS


//力扣 160. 相交链表

//给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
//题目数据 保证 整个链式结构中不存在环。
//注意，函数返回结果后，链表必须 保持其原始结构 。

//思路
//怎么判断相交不相交
//1.把A链表的里的所有结点去跟B链表的结点都比较一遍
//  不是比较值，比较的是结点的地址 
//  暴力比较，时间复杂度是O(N^2)

//2.求出A链表的长度，求出B链表的长度，  
//  链表相交的情况，后缀是一定相等的，只有前面是不一样的。
//  让长的链表先走差距步,然后在同时走，碰到的第一个相同的点，就是相交的点。找相等
//  时间复杂度是O(N)

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
	if (headA == NULL || headB == NULL)
		return NULL;
	//找尾，求长度
	struct ListNode* curA = headA,*curB = headB;
	int lenA = 1, lenB = 1;
	while (curA->next)
	{
		curA = curA->next;
		lenA++;
	}
	while (curB->next)
	{
		curB = curB->next;
		lenB++;
	}

	//比较是否相交
	if (curA != curB)
	{
		return NULL;
	}

	//求交点
	//先找到长的那个链表，先假设一下，* shortList = headA, * longList = headB，再判断
	//如果A>B，那就再交换一下。
	//求差距步，直接用绝对值，不管谁大谁小，用绝对值就行。

	struct ListNode* shortList = headA, * longList = headB;
	if (lenA > lenB)
	{
		shortList = headB;
		longList = headA;
	}
	int gap = abs(lenA - lenB);   //gap差距  abs 绝对值

	//让长的走差距步
	while (gap--)
	{
		longList = longList->next;
	}
	while (shortList != longList)
	{
		shortList = shortList->next;
		longList = longList->next;
	}
	return shortList;

}